// 给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
//
//
//
// 示例 1：
//
//
// 输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
// 输出：[1,2,4,7,5,3,6,8,9]
//
//
// 示例 2：
//
//
// 输入：mat = [[1,2],[3,4]]
// 输出：[1,2,3,4]
//
//
//
//
// 提示：
//
//
// m == mat.length
// n == mat[i].length
// 1 <= m, n <= 10⁴
// 1 <= m * n <= 10⁴
// -10⁵ <= mat[i][j] <= 10⁵
//
// Related Topics 数组 矩阵 模拟 👍 385 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

// Java：对角线遍历
public class P498DiagonalTraverse {
    public static void main(String[] args) {
        Solution solution = new P498DiagonalTraverse().new Solution();
        int[][] mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int[] diagonalOrder = solution.findDiagonalOrder(mat);
        System.out.println(diagonalOrder);
        // TO TEST
    }
    // leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] findDiagonalOrder(int[][] mat) {
            int m = mat.length;
            int n = mat[0].length;
            int i = 0;
            List<Integer> resList = new ArrayList<>();
            while (i < m + n) {

                // 1 3 5趟
                int x1 = i < m ? i : m - 1;
                int y1 = i - x1;
                while (x1 >= 0 && y1 < n) {
                    resList.add(mat[x1][y1]);
                    x1--;
                    y1++;
                }
                i++;

                if (i >= m + n) {
                    break;
                }

                // 246趟

                int y2 = i < n ? i : n - 1;
                int x2 = i - y2;
                while (y2 >= 0 && x2 < m) {
                    resList.add(mat[x2][y2]);
                    x2++;
                    y2--;
                }
                i++;
            }
            int[] res = new int[resList.size()];
            for (int j = 0; j < resList.size(); j++) {
                res[j] = resList.get(j);
            }
            return res;
        }
    }
    // leetcode submit region end(Prohibit modification and deletion)

}
